.. -*- coding: utf-8; -*-

=============================
パラメタ化照合
=============================

パラメタ化照合とはBakerによって定義された文字列の構造に着目した照合を行う手法であり，
ソフトウェアのメンテナンス、プログラムの剽窃の発見、RNAの構造照合などに使われる．

固定するアルファベットを　:math:`\Sigma`　，置き換えを考えるアルファベットを　:math:`\Pi`　とする．
また，パラメタ化文字列を　:math:`\Sigma \cup \Pi`　上の文字列とする．
パラメタ化一致するとは，二つのパラメタ化文字列　:math:`s_1，s_2` に対して，　:math:`\Pi`　から　:math:`\Pi`　への全単射
が存在することをいう．

| 例)
| :math:`\Sigma=\{G,A\}\Pi=\{T,C\}` とし， :math:`s_1=GACCAT，s_2=GATTAC` の二つのパラメタ化文字列を考える．
| :math:`s_1=GACCAT`　について :math:`C \to T，T \to C` を考えると　:math:`s_1 \to GATTAC=s_2`　となるので
| :math:`s_1，s_2`　はパラメタ化一致している．


パラメタ化照合を効率良く行うための符号化としてprev符号が存在している．

.. toctree::
   :maxdepth: 1

   prev